/**
 * 
 */
package org.dse.web;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * This class implements a memory Data Structure for storing graphs.
 * 
 * A large amount of research has recently focused on the graph structure (or
 * link structure) of the World Wide Web, which has proven to be extremely
 * useful for improving the performance of search engines and other tools for
 * navigating the web. For example, the Pagerank algorithm of Brin and Page,
 * used in the Google search engine.
 * 
 * This class provides the methods needed to efficiently compute with graphs and
 * to experiment with the algorithm.
 * 
 * @author zhangchen
 * 
 */
public class WebGraph {

	/**
	 * A Map storing InLinks. For each identifier (the key), another hash set is
	 * stored, containing each inlink.
	 */
	private Map<String, Set<String>> inLinks;

	/**
	 * A Map storing OutLinks. For each identifier (the key), another hash set
	 * is stored, containing each outlink.
	 */
	private Map<String, Set<String>> outLinks;

	/**
	 * Constructor for WebGraph.
	 */
	public WebGraph() {
		inLinks = new HashMap<String, Set<String>>();
		outLinks = new HashMap<String, Set<String>>();
	}

	/**
	 * Add an association between two given nodes in the graph. If the
	 * corresponding nodes do not exists, this method creates them. If the
	 * connection already exists, the strength value is updated.
	 * 
	 * @param fromLink
	 *            The URL for the source node in the graph
	 * @param toLink
	 *            The URL for the target node in the graph
	 */
	public void addLink(String fromLink, String toLink) {
		Set<String> set = outLinks.get(fromLink);
		if (set == null) {
			set = new HashSet<String>();
		}
		set.add(toLink.intern());
		outLinks.put(fromLink.intern(), set);
	}

	/**
	 * Add a link without tolinks in the graph. If the corresponding node do not
	 * exists, this method creates them.
	 * 
	 * @param fromLink
	 *            The URL for the source node in the graph
	 */
	public void addLink(String fromLink) {
		Set<String> set = outLinks.get(fromLink);
		if (set == null) {
			set = new HashSet<String>();
		}
		outLinks.put(fromLink, set);
	}

	/**
	 * Remove a link from the graph.
	 * 
	 * @param link
	 *            The URL to be deleted from the graph
	 */
	public void removeLink(String link) {
		outLinks.remove(link);
	}

	/**
	 * Finish construting the web graph. It means to add reverse associations
	 * according to the associations. The original association means a page
	 * refers to other pages. The reverse association means a page is referred
	 * by other pages.
	 */
	public void finishConstruction() {
		for (String fromLink : outLinks.keySet()) {
			inLinks.put(fromLink, new HashSet<String>());
		}

		for (String fromLink : outLinks.keySet()) {
			Set<String> toLinks = outLinks.get(fromLink);

			for (Iterator<String> it = toLinks.iterator(); it.hasNext();) {
				String toLink = it.next();
				if (!outLinks.containsKey(toLink)) {
					it.remove();
					continue;
				}

				Set<String> set = inLinks.get(toLink);

				if (set == null) {
					set = new HashSet<String>();
				}

				set.add(fromLink.intern());
				inLinks.put(toLink.intern(), set);
			}

			outLinks.put(fromLink, toLinks);
		}
	}

	/**
	 * Return a Map of the nodes that connect to a given node in the graph. Each
	 * mapping contains the identifyer for a node and the associated connection
	 * strength.
	 * 
	 * @param URL
	 *            The URL for the node in the graph
	 * @return A Map of the nodes that connect to the given node in the graph.
	 */
	public Set<String> inLinks(String URL) {
		Set<String> set = inLinks.get(URL.intern());
		return (set == null) ? new HashSet<String>() : set;
	}

	/**
	 * Return a Map of the nodes that are connected from a given node in the
	 * graph. Each mapping contains the identifyer for a node and the associated
	 * connection strength.
	 * 
	 * @param URL
	 *            The URL for the node in the graph
	 * @return A Map of the nodes that are connected from the given node in the
	 *         graph.
	 */
	public Set<String> outLinks(String URL) {
		Set<String> set = outLinks.get(URL.intern());
		return (set == null) ? new HashSet<String>() : set;
	}

	/**
	 * Return the number of nodes in the graph.
	 * 
	 * @return the number of nodes in the graph
	 */
	public int numNodes() {
		return outLinks.keySet().size();
	}

	/**
	 * Return the url of each node.
	 * 
	 * @return the url string of each node
	 */
	public Set<String> availableLink() {
		return outLinks.keySet();
	}

}
